package com.wc.算法基础课.D第四讲数学知识.求组合数.杨辉三角形;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/4/7 15:22
 * @description https://www.acwing.com/problem/content/3421/
 */
public class Main {
    static int n;

    // 寻找C(2 * k, k)
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int k = 16; ; k--) {
            if (check(k))
                break;
        }
    }

    static boolean check(int k) {
        long l = 2L * k, r = n;
        if (l > r) return false;
        while (l < r) {
            long mid = l + r >> 1;
            if (C(mid, k) >= n) r = mid;
            else l = mid + 1;
        }
        if (C(r, k) != n) return false;
        System.out.println(r * (r + 1) / 2 + k + 1);
        return true;
    }

    static long C(long a, int b) {
        long res = 1;
        for (long i = a, j = 1; j <= b; i--, j++) {
            res = res * i / j;
            if (res > n) return res;
        }
        return res;
    }
}
